package esercitazione3.tda_RBTree;

import esercitazione3.exceptions.InvalidPositionException;
import esercitazione3.tda_BinaryTree.BTPosition;
import esercitazione3.tda_BinaryTree.BinarySearchTree;
import esercitazione3.tda_BinaryTree.EmptyTreeException;
import esercitazione3.tda_Dictionary.Dictionary;
import esercitazione3.tda_Dictionary.Entry;
import esercitazione3.tda_Dictionary.InvalidKeyException;


/**
 * La classe rappresenta un singolo albero RB.
 * Estende l'albero BST e dipende da oggetti generici K (necessariamente comparabili) e V.
 * Gli oggetti generici K e V sono usati come coppia chiave valore, accessibile grazie all'implementazione
 * dell'interfaccia Dictionary.
 *
 * @param <K>
 * @param <V>
 */
public class RBTree<K extends Comparable<K>, V> extends BinarySearchTree<K, V> implements Dictionary<K, V> {

	
	/**
	 * Costruttore vuoto, che richiama il costruttore di default dell'albero BST.
	 */
	public RBTree() {
		super();
	}

	
	/**
	 * Metodo che sovrascrive quello di LinkedBT che restituiva semplicemente un nodoBT generico.
	 * Questo metodo invece restiuisce un nodoRB e lo restituisce NERO.
	 */
	@Override
	protected BTPosition<Entry<K, V>> createNode(Entry<K, V> element, BTPosition<Entry<K, V>> parent, BTPosition<Entry<K, V>> left, BTPosition<Entry<K, V>> right) {
		RBNode<Entry<K, V>> n = new RBNode<Entry<K, V>>(element, parent, left, right);
		n.makeBlack();
		return n;
	}

	 
	/**
	 * Metodo per inserire un nodo all'interno dell'albero.
	 * Sovrascrive il metodo degli alberiBST
	 * (che comunque viene usato nell'implementazione e inserisce come nodo esterno dell'albero)
	 *
	 * il metodo poi, ottenuto il nodo tramite Position (chiedo l'entry, ottengo l'intero nodo che lo contiene),
	 * lo rende ROSSO per non modificare l'altezza nera.
	 *
	 * Infine dopo l'inserimento il metodo FIX ripristina eventualmente l'altezza nera dell'albero e le regole dei RBT
	 */
	@Override
	public Entry<K, V> insert(K k, V v) throws InvalidKeyException {
		BSTEntry<K, V> entry = (BSTEntry<K, V>) super.insert(k, v);
		RBNode<Entry<K, V>> node = (RBNode<Entry<K, V>>) entry.position();
		node.makeRed();

		try {
			insertFixUp(node);
		} catch (ClassCastException e) {
			e.printStackTrace();
		} catch (InvalidPositionException e) {
			e.printStackTrace();
		} catch (EmptyTreeException e) {
			e.printStackTrace();
		}
		return entry;
	}

	/**
	 * Rotazione a sinistra sul nodo desiderato
	 * 
	 * @param node (node è considerato nodo padre nella terminologia.)
	 * @throws ClassCastException
	 * @throws InvalidPositionException
	 */
	private void leftRotation(RBNode<Entry<K, V>> node) throws ClassCastException, InvalidPositionException {
		// controllo se esiste un Nonno, se esiste controllo se il Padre è
		// figlio destro (o sinistro)
		// e assegno come figlio destro (o sinistro) il Figlio.
		if (node.getParent() != null)
			if (node==node.getParent().getLeft())
				node.getParent().setLeft(node.getRight());
			else
				node.getParent().setRight(node.getRight());
		else
			setRoot(node.getRight());

		// assegno il Nonno come padre del Figlio
		node.getRight().setParent(node.getParent());

		// assegno il figlio come padre del padre
		node.setParent(node.getRight());

		// assegno figlio destro del Padre il figlio sinistro del Figlio.
		node.setRight(node.getRight().getLeft());

		// assegno come padre del figlio sinistro del Figlio (se esiste) il
		// Padre
		if (node.getRight() != null)
			node.getRight().setParent(node);

		// assegno il Padre come figlio del Figlio
		node.getParent().setLeft(node);
	}

	/**
	 * Rotazione a destra sul nodo desiderato
	 * @param node (node è considerato nodo padre nella terminologia)
	 * @throws ClassCastException
	 * @throws InvalidPositionException
	 */
	private void rightRotation(RBNode<Entry<K, V>> node) throws ClassCastException, InvalidPositionException {
		// controllo se esiste un Nonno, se esiste controllo se il Padre è
		// figlio destro (o sinistro)
		// e assegno come figlio destro (o sinistro) il Figlio.
		if (node.getParent() != null)
			if (node==node.getParent().getLeft())
				node.getParent().setLeft(node.getLeft());
			else
				node.getParent().setRight(node.getLeft());
		else
			setRoot(node.getLeft());

		// assegno il Nonno come padre del Figlio
		node.getLeft().setParent(node.getParent());

		// assegno il figlio come padre del padre
		node.setParent(node.getLeft());

		// assegno figlio sinistro del Padre il figlio destro del Figlio.
		node.setLeft(node.getLeft().getRight());

		// assegno come padre del figlio destro del Figlio (se esiste) il Padre
		if (node.getLeft() != null)
			node.getLeft().setParent(node);

		// assegno il Padre come figlio del Figlio
		node.getParent().setRight(node);
	}

	/**
	 * Metodo RICORSIVO per bilanciare l'albero dopo un inserimento normale di un nodo ROSSO
	 * @param node Nodo dal quale parte il rebilanciamento dell'albero
	 * @throws ClassCastException
	 * @throws InvalidPositionException
	 * @throws EmptyTreeException
	 */
	public void insertFixUp(RBNode<Entry<K, V>> node) throws ClassCastException, InvalidPositionException, EmptyTreeException{
		// CASO 1: node è root
		// ALLORA node deve essere NERO
		if (node.getParent() != null){
			// CASO 2: se padre è nero, ALLORA inserimento corretto
			// altrimenti se padre è rosso...
			if(node.getParent().isRed()){
				// se esiste un nonno e esiste uno zio
				// CASO 3: lo zio è ROSSO, e quindi il nonno è sicuramente NERO
				// ALLORA coloro lo zio e il padre di NERO e il nonno di ROSSO
				if(node.getGrandfather() != null && node.getParent() == node.getGrandfather().getLeft()){
					RBNode<Entry<K, V>> uncle = node.getUncle();
					if(uncle.isRed()){
						node.getParent().makeBlack();
						uncle.makeBlack();
						node.getGrandfather().makeRed();
						node = node.getGrandfather();
						// Invoco la ricorsione sul nonno che adesso è ROSSO
						insertFixUp(node);
					}
					// lo zio è NERO (poichè non è entrato nel blocco if)
					// e il padre è ROSSO (altrimenti l'inserimento era corretto al CASO 2)
					//
					// CASO 4: il nodo è figlio destro del padre
					// ALLORA ruoto a sinistra
					else if(node == node.getParent().getRight()){
						node = node.getParent();
						leftRotation(node);
						// Invoco la ricorsione sul padre dopo aver ruotato a sinistra
						insertFixUp(node);
					}
					// CASO 5: il nodo è figlio sinistro del padre
					// ALLORA ruoto a destra
					else{
						node.getParent().makeBlack();
						node.getGrandfather().makeRed();
						rightRotation(node.getGrandfather());
					}
				}
				// Procedimento uguale al precedente
				// ma questa volta il padre è figlio destro e lo zio figlio sinistro
				else if(node.getGrandfather() != null){
					RBNode<Entry<K, V>> uncle = node.getUncle();
					if(uncle.isRed()){
						node.getParent().makeBlack();
						uncle.makeBlack();
						node.getGrandfather().makeRed();
						node = node.getGrandfather();
						// Invoco la ricorsione sul nonno che adesso è ROSSO
						insertFixUp(node);
					}
					// lo zio è NERO (poichè non è entrato nel blocco if)
					// e il padre è ROSSO (altrimenti l'inserimento era corretto al CASO 2)
					//
					// CASO 4: il nodo è figlio sinistro del padre
					// ALLORA ruoto a destra
					else if(node == node.getParent().getLeft()){
						node = node.getParent();
						rightRotation(node);
						// Invoco la ricorsione sul padre dopo aver ruotato a sinistra
						insertFixUp(node);
					}
					// CASO 5: il nodo è figlio destra del padre
					// ALLORA ruoto a sinistra
					else{
						node.getParent().makeBlack();
						node.getGrandfather().makeRed();
						leftRotation(node.getGrandfather());
					}
				}
			}
		}
		// CASO 1: se node è la root (cioè non ha padre)
		// ALLORA il nodo/root deve essere NERO
		RBNode<Entry<K, V>> x = (RBNode<Entry<K, V>>) root();
		x.makeBlack();
	}

	/**
	 * Metodo ITERATIVO per bilanciare l'albero dopo un inserimento normale di un nodo ROSSO
	 * @param node Nodo dal quale parte il rebilanciamento dell'albero
	 * @throws ClassCastException
	 * @throws InvalidPositionException
	 * @throws EmptyTreeException
	 */
	private void insertFixUpIterative(RBNode<Entry<K, V>> node) throws ClassCastException, InvalidPositionException, EmptyTreeException{
		// se node non è la root
		if(node.getParent() != null)
			// CASO 2: se il padre è nero
			// ALLORA io aggiungo un nodo rosso, e quindi l'inserimento è corretto
			// altrimenti devo entrare nel ciclo (con padre rosso quindi)
			while(node.getParent() != null && node.getParent().isRed()){
				// se esiste un nonno e esiste uno zio
				// CASO 3: lo zio è ROSSO, e quindi il nonno è sicuramente NERO
				// ALLORA coloro lo zio e il padre di NERO e il nonno di ROSSO
				if(node.getGrandfather() != null && node.getParent() == node.getGrandfather().getLeft()){
					RBNode<Entry<K, V>> y = node.getGrandfather().getRight();
					if(y.isRed()){
						node.getParent().makeBlack();
						y.makeBlack();
						node.getGrandfather().makeRed();
						node = node.getGrandfather();
					}
					// lo zio è NERO (poichè non è entrato nel primo if)
					// e il padre è ROSSO (per condizione del ciclo)
					// CASO 4: il nodo è figlio destro del padre
					// ALLORA ruoto a sinistra
					else if(node == node.getParent().getRight()){
						node = node.getParent();
						leftRotation(node);
					}
					// CASO 5: il nodo è figlio sinistro del padre
					// ALLORA ruoto a destra
					else{
						node.getParent().makeBlack();
						node.getGrandfather().makeRed();
						rightRotation(node.getGrandfather());
					}
				}
				// Procedimento uguale al precedente
				// ma questa volta il padre è figlio destro e lo zio figlio sinistro
				else if(node.getGrandfather() != null){
					RBNode<Entry<K, V>> y = node.getGrandfather().getLeft();
					if(y.isRed()){
						node.getParent().makeBlack();
						y.makeBlack();
						node.getGrandfather().makeRed();
						node = node.getGrandfather();
					}
					else if(node == node.getParent().getLeft()){
						node=node.getParent();
						rightRotation(node);
					}
					else{
						node.getParent().makeBlack();
						node.getGrandfather().makeRed();
						leftRotation(node.getGrandfather());
					}

				}
			}
		// CASO 1: se node è la root (cioè non ha padre)
		// ALLORA il nodo/root deve essere NERO
		RBNode<Entry<K, V>> x = (RBNode<Entry<K, V>>) root();
		x.makeBlack();
	}

	
	/**
	 * Metodo per stampare ogni elemento dell'albero
	 * @param node Nodo da cui si vuole far partire la stampa del sottoalbero
	 * @throws InvalidPositionException
	 */
	public void stampa(RBNode<Entry<K, V>> node) throws InvalidPositionException {
		if (node.element() == null)
			return;
		System.out.println(this.toString());
	}

	/**
	 * Metodo per ottenere l'albero come una stringa
	 */
	@Override
	public String toString() {
		try {
			return toString((RBNode<Entry<K, V>>)this.root(), "") + "\n";
		} catch (EmptyTreeException e) {
			e.printStackTrace();
		}
		return null;
	}

	
	/**
	 * Metodo ricorsivo per ottenere tutti i nodi dell'albero come una stringa
	 * @param node
	 * @param indent
	 * @return
	 */
	private String toString(RBNode<Entry<K, V>> node, String indent) {
		String s = "";

		if(node.getLeft() != null)
			s += toString(node.getLeft(), indent + "     ");
		try {
			if(node.element() != null)
				s += indent + node.element().getKey() + " - " + node.element().getValue()  + " (" + node.color + ")" + "\n";
		} catch (InvalidPositionException e) {
			e.printStackTrace();
		}
		if(node.getRight() != null)
			s += toString(node.getRight(), indent + "     ");

		return s;
	}
}
